package com.kele;

import java.util.Arrays;

/**
 * @ClassName : BubleSort
 * @Author : kele
 * @Date: 2022/11/3 23:35
 * @Description :
 */
public class BubleSort {

    /**
     * 冒泡排序
     *
     * @param input
     */
    public static void sortV1(int[] input) {
        //排序轮次，需要排数组长度相同的轮
        for (int i = 0; i < input.length - 1; i++) {
            //每轮需要对每两个相邻的元素进行比较，每次确定一个元素，所以最大的要-i
            for (int j = 0; j < input.length - 1 - i; j++) {
                if (input[j] > input[j + 1]) {
                    //交换左右的值
                    int tmp = input[j + 1];
                    input[j + 1] = input[j];
                    input[j] = tmp;
                }//否则不作任何处理
            }
        }
    }

    /**
     * @param input
     */
    public static void sortV2(int[] input) {

        for (int i = 0; i < input.length - 1; i++) {
            //设置一个标签，如果在该标签内没有交换的元素，证明前面的元素都已经排好序了
            boolean flag = true;
            //每轮需要对每两个相邻的元素进行比较，每次确定一个元素，所以最大的要-i
            for (int j = 0; j < input.length - 1 - i; j++) {
                if (input[j] > input[j + 1]) {
                    //交换左右的值
                    int tmp = input[j + 1];
                    input[j + 1] = input[j];
                    input[j] = tmp;
                    flag = false;
                }//否则不作任何处理
            }
            //由于本轮没有交换的元素，证明本轮及本轮之后的元素都已经是排好序的，直接跳出
            if (flag) break;
        }
    }

    /**
     * @param input
     */
    public static void sortV3(int[] input) {
        //lastPoint和savePoint作为内循环的结尾的地方，即：在这之后我都已经排序好了，不要对我循环了，
        int lastPoint = input.length - 1;
        int savePoint = lastPoint;
        for (int i = 0; i < input.length - 1; i++) {
            //设置一个标签，如果在该标签内没有交换的元素，证明前面的元素都已经排好序了
            boolean flag = true;
            for (int j = 0; j < savePoint; j++) {
                if (input[j] > input[j + 1]) {
                    int tmp = input[j + 1];
                    input[j + 1] = input[j];
                    input[j] = tmp;
                    flag = false;
                    lastPoint = j;
                }//否则不作任何处理
            }
            //保存一下最后的位置
            savePoint = lastPoint;
            //由于本轮没有交换的元素，证明本轮及本轮之后的元素都已经是排好序的，直接跳出
            if (flag) break;
        }
    }

    public static void main(String[] args) {

        int[] input = {6, 4, 7, 9, 3, 5, 0, 2, 1, 8};
        int[] input2 = {4,6,2,7,9,1,3,0,8,5};

        sortV3(input2);
        System.out.println(Arrays.toString(input2));


    }
}
